package com.leetcode;


/**
 * 1653. 使字符串平衡的最少删除次数 (中等)
 * 给你一个字符串 s ，它仅包含字符 'a' 和 'b' 。
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。
 * 请你返回使 s 平衡 的 最少 删除次数。
 */
public class LeetCode1653 {

    public static void main(String[] arg0) {
        String s = "bbaaaaabb";
        System.out.println("使 s 平衡 的 最少 删除次数 = " + minimumDeletions(s));
    }

    /**
     * 符合结果条件必须全是a或者全是b，或者在某一分割线左边全是a，右边全是b
     */
    public static int minimumDeletions(String s) {
        int leftb = 0;
        int righta = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') righta++;
        }

        int res = righta;
        for (int i = 0; i < s.length(); i++) {
            if (i == 0 && (righta == 0 || righta == s.length())) {
                res = 0;
                break;
            }
            if (s.charAt(i) == 'b') {
                leftb++;
            } else if (s.charAt(i) == 'a') {
                righta--;
            }
            res = Math.min(res, leftb + righta);
        }
        return res;
    }


}
